#include "HP.h"

void HP_init(HP* p)
{
    assert(p);
    p->capacity = 0;
    p->size=0;
    p->array=NULL;
}
void HP_push(HP*p, HPdatatype x)//增加数据
{
    assert(p);
    if(p->size>=p->capacity)
    {
        p->capacity = p->capacity == 0? 4:2*p->capacity;
        HPdatatype* newp = (HPdatatype*)realloc(p->array,sizeof(HPdatatype)*p->capacity);
        if(!newp)
        {
            perror("malloc fail");
            return;
        }
        p->array = newp;
    }
    p->array[p->size++] = x;
    int t = p->size-1;
    adjust_up(p->array,t,1,p->size);
    return ;
}


int heapempty(HP* p)
{
    assert(p);
    if(p->size<=0)
    {
        return 1;
    }
    return 0;
}

void headpop(HP* p)//delete the top of the heap
{
    assert(p);
    assert(!heapempty(p));
    swap(&p->array[0],&p->array[--p->size],sizeof(HPdatatype));
    adjust_down(p->array,0,1,p->size);
    return ;
}
void swap(void* e1,void*e2,int width)
{
    char* t1 = (char*)e1;
    char* t2 = (char*)e2;
    for(int i = 0;i<width;i++)
    {
        char t =  t1[i];
        t1[i] = t2[i];
        t2[i] = t;
    }
    return ;
}

void adjust_up(int* a,int pos_now,int is_little,int size)//向上调整
{
    if(size==1)
    {
        return;
    }
    int i = pos_now;
    if(is_little>0)
    {
        while(i-1>=0 && a[(i-1)/2]<a[i])
        {
            swap(&a[(i-1)/2],&a[i],sizeof(int));
            i = (i-1)/2;
        } 
    }
    else
    {
        while(i-1>=0 && a[(i-1)/2]>a[i])
        {
            swap(&a[(i-1)/2],&a[i],sizeof(int));
            i = (i-1)/2;
        } 
    }
    return;
}


void adjust_down(int* a,int pos_now,int is_little,int size)//向下调整
{
    int i = pos_now;
    if(is_little>0)
    {
        int j = i*2+1;
        while(j<size)
        {
            if(j+1<size && a[j+1]>a[j])
            {
                j++;
            }
            if(a[j]>a[i])
            {
                swap(&a[i],&a[j],sizeof(int));
            }
            else
            {
                break;
            }
            i = j;
            j = i*2+1;
        }
    }
    else
    {
        int j = i*2+1;
        while(j<size)
        {
            if(j+1<size && a[j+1]<a[j])
            {
                j++;
            }
            if(a[j]<a[i])
            {
                swap(&a[i],&a[j],sizeof(int));
            }
            else
            {
                break;
            }
            i=j;
            j = i*2+1;
        }
    }
}
HPdatatype heaptop(HP* p)
{
    assert(p);
    assert(!heapempty(p));
    return p->array[0]; 
}